package class08_trietree;

/**
 * 前缀树
 */
public class Test01_TrieTree {

    public static class Node {
        public int pass;
        public int end;
        public Node[] nexts;

        /**
         * 构造器：因为每个节点的pass 和 end 初始化的时候都为0，所以在构造方法中可以写死；
         * 又因为 nexts 最多有26个英文字母，所以初始化的时候也可以写死
         * 这个节点只是适用与 abcd 26个英文字母
         */
        public Node() {
            this.pass = 0;
            this.end = 0;
            this.nexts = new Node[26];
        }
    }

    /**
     * 前缀树
     */
    public static class Trie {
        public Node root;

        /**
         * 前缀树初始化的时候就是一个Node节点
         */
        public Trie() {
            this.root = new Node();
        }


        /**
         * 插入字符串
         *
         * @param word
         */
        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] str = word.toCharArray();
            Node node = root;
            node.pass++;
            for (int i = 0; i < str.length; i++) {
                int path = str[i] - 'a';
                if (node.nexts[path] == null) {
                    node.nexts[path] = new Node();
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;

        }

        public void delete(String word) {
        }

        /**
         * word 这个单词之前加入过几次
         *
         * @param word
         * @return
         */
        public int search(String word) {
            return 0;
        }

        /**
         * 之前加入的字符串中，有多少是以pre开头的呢
         *
         * @param pre
         * @return
         */
        public int prefixNumb(String pre) {
            return 0;
        }
    }
}
